/*
 * @lc app=leetcode.cn id=96 lang=cpp
 *
 * [96] 不同的二叉搜索树
 */

#include <limits.h>

#include <iostream>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;

// @lc code=start
class Solution {
public:
    int numTrees(int n) {
        vector<int> counter(n + 1, 0);      // 记录一定区间长度的二叉搜索树种数

        // 初始元素
        counter[0] = 1;
        counter[1] = 1;

        // 动态规划
        // i表示区间长度
        for (int i = 2; i <= n; i++) {
            int tmp = 0;
            // j 表示左子树区间长度，范围为[0, i-1]
            for (int j = 0; j < i; j++) {
                // k 表示右子树区间长度
                int k = i - 1 - j;
                tmp = tmp + counter[j] * counter[k];
            }
            counter[i] = tmp;
        }
        
        return counter[n];
    }
};
// @lc code=end

